package com.lee.algorithm.array;

/***
 * @description: 二分查找
 *      左闭右开[left, right)
 *          right = arr.length - 1
 *          while(left < right)
 *          right = mid
 *          left = mid + 1
 *      左闭右闭[left, right]
 *          right = arr.length
 *          while(left <= right)
 *          right = mid - 1
 *          left = mid + 1
 * @author : 青石路
 * @date: 2021/11/22 14:59
 */
public class BinarySearch {

    /**
     * 有序数组中，找某个数是否存在
     * arr 必须是有序的
     * @param arr
     * @param obj
     * @return
     */
    public static int binarySearch(int[] arr, int obj) {

        if (arr == null) {
            return -1;
        }

        int left = 0, right = arr.length-1;
        while (left < right) {              // 定义 obj 在左闭右开的区间里，即：[left, right)
            int mid = (left + right) >> 1;
            if (arr[mid] > obj) {
                right = mid;
            } else if (arr[mid] < obj) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 在一个有序数组中，找 >= 某个数最左侧的位置
     * @param arr
     * @param target
     * @return
     */
    public static int binarySearch2(int[] arr, int target) {

        if (arr == null || arr.length < 1) {
            return -1;
        }

        int left = 0, right = arr.length-1;
        while(left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return arr[right] >= target ? right : -1;
    }

    /**
     * 局部最小值问题
     *      无序数组中，任何两个相邻的数不相等
     *      i-1 > i < i+1，i位置上的元素就是局部最小
     *      找出一个满足条件的位置
     * @param arr
     * @return
     */
    public static int binarySearch3(int[] arr) {

        if (arr == null || arr.length <= 1) {
            return -1;
        }

        if(arr[0] < arr[1]) {
            return 0;
        }

        if (arr[arr.length - 2] > arr[arr.length-1]) {
            return arr.length - 1;
        }

        int left = 1, right = arr.length - 2;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }

    /**
     * 搜索插入位置
     *      给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置
     *
     *      左闭右闭
     * @param arr
     * @param target
     * @return
     */
    public static int searchInsert(int[] arr, int target) {

        if (arr == null) {
            return 0;
        }
        int left = 0, right = arr.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) {
                right = mid - 1;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return right + 1;
    }

    /**
     * 搜索插入位置
     *
     *      左闭右开
     * @param arr
     * @param target
     * @return
     */
    public static int searchInsert2(int[] arr, int target) {

        if (arr == null) {
            return 0;
        }
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] > target) {
                right = mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return right;
    }

    public static void main(String[] args) {
        /*int[] arr = new int[]{3,1,2,3,4,5,6};
        int index = binarySearch3(arr);
        System.out.println("index = " + index);*/

        int[] arr = new int[]{1,3,5,7,9,13,17,17,28};
        int[] range = searchRange(arr, 17);
        System.out.println("range = " + range[0] + " " + range[1]);
    }

    /**
     * 在排序数组中查找元素的第一个和最后一个位置
     *      给定一个按照升序排列的整数数组 arr，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置
     *      如果数组中不存在目标值 target，返回 [-1, -1]
     *
     *      左一直往下二分找到开始位置
     *      右一直往下二分找到结束位置
     * @param arr
     * @param target
     * @return
     */
    public static int[] searchRange(int[] arr, int target) {
        if (arr == null) {
            return new int[]{-1,-1};
        }
        int leftIndex = searchLeft(arr, 0, arr.length, target);
        int rightIndex = searchRight(arr, 0, arr.length, target);
        return new int[]{leftIndex, rightIndex};
    }

    /**
     * 左闭右开，一直往左分，直至分不下去
     *      与 binarySearch2 一致，找 >= target 最左侧的位置
     * @param arr
     * @param left
     * @param right
     * @param target
     * @return
     */
    public static int searchLeft(int arr[], int left, int right, int target) {
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(arr[mid]>=target) {
                right=mid;
            } else {
                left=mid+1;
            }
        }
        if(right == arr.length) {
            return -1;
        }
        return arr[right] == target ? right : -1;
    }

    /**
     * 左闭右开，一直往右分，直至分不下去
     *      与 binarySearch2 类似，找 <= target 最右侧的位置
     * @param arr
     * @param left
     * @param right
     * @param target
     * @return
     */
    // 1,3,5,7,9,13,17,17,28
    public static int searchRight(int arr[], int left, int right, int target) {
        int rightIndex = -1;
        while(left<right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] <= target){
                rightIndex = mid;
                left = mid+1;
            } else {
                right = mid;
            }
        }
        if (rightIndex == -1) {
            return rightIndex;
        }
        return arr[rightIndex] == target ? rightIndex : -1;
    }
}
